package pro.softzhang.algo.lc200;

import pro.softzhang.algo.common.TrieNode;
import pro.softzhang.algo.flag.knowledge.KPrefixTree;
import pro.softzhang.algo.flag.theme.TDesign;

@TDesign
@KPrefixTree
public class LC208_ImplementTriePrefixTree {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Trie {

        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if(node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            node.isWord = true;
        }

        public boolean search(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if(node.children[idx] == null) {
                    return false;
                }
                node = node.children[idx];
            }
            return node.isWord;
        }

        public boolean startsWith(String prefix) {
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
                int idx = c - 'a';
                if(node.children[idx] == null) {
                    return false;
                }
                node = node.children[idx];
            }
            return true;
        }
    }
}